Abstract: The minimum linear ordering problem (MLOP) seeks to minimize an aggregated cost f(·) due to an ordering σ of the items (say [n]), i.e., $min_σ f(S_{i,\sigma})$, where $S_{i,\sigma}$ is the set of items that are mapped by $\sigma$ to indices at most $i$. This problem has been studied in the literature for various special cases of the cost function f, and in a general setting for a submodular or supermodular cost f [Iwata, Tetali, and Tripathi '12]. We expand the machinery for approximating monotone submodular MLOP (by a factor of 2) and minimum latency vertex cover (by a factor of 4/3) and present first NP-hardness results for (special cases of) these problems. Our algorithm for monotone submodular MLOP is parameterized, using theory of principal partitions, and specifically for matroid MLOP leads to a 2 - (1+rank)/(1+size) approximation. Finally we discuss some open problems and new directions in this line.
References: arXiv:2108.00914, arXiv:2007.09172